/**
 * 39. 组合总和
 * 
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates
 * 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
 * 
 * 说明：
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 * 
 * 示例 1：
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为：
 * [
 *  [7],
 *  [2,2,3]
 * ]
 *
 * 示例 2：
 * 输入：candidates = [2,3,5], target = 8,
 * 所求解集为：
 * [
 *  [2,2,2,2],
 *  [2,3,3],
 *  [3,5]
 * ]
 * 
 * 提示：
 * 1 <= candidates.length <= 30
 * 1 <= candidates[i] <= 200
 * candidate 中的每个元素都是独一无二的。
 * 1 <= target <= 500
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 */

package zw;

import java.util.ArrayList;
import java.util.List;

public class T39 {
	public static List<List<Integer>> combinationSum(int[] candidates, int target) {
		sort(candidates);
		ArrayList<Integer> res = new ArrayList<>(); 
		List<List<Integer>> resList = new ArrayList<>();
		combination(candidates, 0, target, res, resList);
		return resList;
    }
	
	private static void combination(int[] candidates,int index, int target, ArrayList<Integer> res, List<List<Integer>> resList) {
		if(target == 0) {
			resList.add(new ArrayList<Integer>(res));
		}
		for(int i = index; i < candidates.length; i++) {
			if(target >= candidates[i]) {
				res.add(candidates[i]);
				combination(candidates, i ,target-candidates[i], res, resList);
				res.remove(res.size()-1);
			} else {
				break;
			}
		}
	}
	
	private static int[] sort(int[] array) {
		for(int i = array.length; i > 0; i--) {
			for(int j = 1; j < i; j++) {
				if(array[j-1] > array[j]) {
					int tmp = array[j];
					array[j] = array[j-1];
					array[j-1] = tmp;
				}
			}
		}
		return array;
	}
	
	public static void main(String[] args) {
		System.out.print(combinationSum(new int[] {2,3,5}, 8).toString());
	}
}
